算法分析神器—时间复杂度
窗外风雪再大
也有我陪伴着你
时间复杂度是学习算法的基石，今天我们来聊聊为什么要引入时间复杂度，什么是时间复杂度以及如何去算一个算法的时间复杂度
刻画算法的运行时间
某日，克叫来了慧子打算给他补习补习一下基础知识，只见克写了一段非常简单的代码
克
你说一下这段代码会运行多长时间
这个...，得在计算机上跑一下才可以知道吧
慧子
克
恩恩，对的，那如果我改变n的大小为10000，你能够预测它的运行时间吗？
这个...,要不再测一次
慧子
克面无表情
克
我们要善于发现事物的内在规律
克看了一下慧子
这个程序的内在规律是什么呢？
慧子
慧子看老师有点生气，开始虚心请教了
克
你要预测当n=10000的时候，这个程序会运行多长时间，你首先要知道程序的运行时间都花在哪了？
克
当电脑运行这段代码的时候，执行任何一条语句都需要花费时间，这是时间花费的主要地方
为了方便讨论，这里我们把每一条语句的执行时间都看做是一样的，记为一个时间单元
克
你看一下刚才的程序都有哪些语句
克
你看，这个程序有这么几个地方消耗了时间
① 蓝色框的两条语句，花费两个时间单元
②黑色框的一条语句，花费n+1个时间单元
③红色框的两条语句，花费2*n个时间单元
克
那么一共花费了3n+3个时间单元,可以看出，程序消耗的时间和你的n成线性关系
这不是数学吗，慧子心里想到
克
现在我用T(n)表示这个程序运行了多长时间，那么这个程序运行的时间就可以写成T(n)=3n+3
其中的n被我们称为问题的规模，其实就是你处理问题的大小
克顺手画了这个函数的图
本文主要讨论问题规模和运行时间的关系，假定不同输入和运行时间基本无关
哦，我懂了，要预测程序的时间，我可以把运行时间函数求出来
慧子
克
恩恩，对的
这个函数表达式看起来挺复杂的
慧子
克
我们常常会对这个函数进行简化，使得它既简单又不失函数的主要特性
哦？怎么简化
慧子
时间复杂度
克
我们一般只关心随着问题规模n趋于无穷时函数中对函数结果影响最大的项，也就是最高次项
比如说：T(n)=3n+3,当n非常大的时候常数3和n的系数3对函数结果的影响就很小了
克
所以一般我们会保留最高次项并忽略该项的系数
比如： T(n)=n+1 忽略常数项 T(n)~n T(n)=n+n^2 忽略低阶项 T(n)~n^2
T(n)=3n 忽略最高阶的系数 T(n)~n
这个忽略低阶项是什么意思
慧子
克
所谓低阶项，简单地说就是当n非常大时，这个项相对于另外一个项很小，可以忽略，比如n相对于n^2,n就是低阶项
哦，我怎么判断哪个是高阶，哪个是低阶呢？
慧子
克
具体要用数学知识，对你而言，你只需记住下面的大小关系就行了，到时按照这个进行忽略（相对较小的忽略）
还好不用掌握那头疼的数学，慧子心中想到
简化完了之后呢？
慧子
慧子把话题又拉了回来
克
化简完后的函数可以近似地代表原来函数的总体趋势
克
简化后的式子被称为这个程序算法的时间复杂度，记做O(f(n)),f(n)就是简化后的式子，比如说刚开始讨论的T(n)=3n+3,简化后T(n)~f(n)=n,那我们记为O(n)
更准确地说O代表了运行时间函数的一个渐进上界，即T(n)在数量级上小于等于f(n)
哦，原来时间复杂度可以表示某个算法的运行时间的趋势，大致地度量算法效率的好坏， 那我该如何算这个时间复杂度呢？
慧子
时间复杂度的计算
克
从前面可以总结出计算算法复杂度大O的方法
一、得出运行时间的函数 二、对函数进行简化
①用常数1来取代运行时间中所有加法常数
②修改后的函数中，只保留最高阶项 ③如果最高阶项存在且不是1，则忽略这个项的系数
克
举个例子吧，先来看这样一段代码
克
显然，T(n)=3,对这个函数进行简化，用常数1取代常数3，然后取代后的函数没有最高阶项，那么这个算法的时间复杂度就是O(1).
O(1)也被称为常数阶
每次都要把时间函数算出来，好复杂，有没有简便一点的方法
慧子
克
这个还真可以耍耍小聪明，一般来说，最内层执行次数最多的语句就决定了整个算法的趋势
克
你只要看看最内层的语句执行次数的规律就行了，这个内层打印语句随着问题规模n的增加会呈线性增加，直接就可以判定复杂度为O(n)
这个方法真棒，那么按照这个方法就很容易得出下面这个嵌套的两层for循环的复杂度为O（n^2）了
慧子
慧子随手写了一段嵌套循环的代码
克
恩恩，对的，最内层的语句随n的增加会呈二次函数的规律执行，代表了这个算法执行时间的一个趋势
我听说有一个很神奇的函数叫对数函数，它随着自变量的增大，因变量增长的很慢，这个应该很受欢迎吧
慧子
克
嗯嗯，对的，对数函数的趋势显然比线性函数好(对数函数随着自变量的增大因变量增长的很慢)
接着，克又写了一段时间复杂度为对数的代码
克
你看，这段代码的复杂度就为对数级别的，O(logn)
这个怎么分析
慧子
一向数学不太好的谦子此时有点懵
克
和之前的分析方法一样，我们着重看执行次数最多的内层代码语句
克
每循环一次，sum就给自身乘以2，乘了多少次就跳出循环了呢(大于等于n)？不知道，就设为x吧，那么2^x=n,解出x=logn，这说明随着n的增大，最消耗时间的内层语句是呈指数变化的
哦，我懂了，原来如此
慧子
克
复杂度的内容很多，你只要理解它的含义以及会分析简单的算法就行了，以后遇到复杂的，为师会给你传授的
好的
慧子
慧子与老师道了别